package Javafoundation;

import java.util.*;

public class Looptest {
    private Map<String, List<String>> graph = new HashMap<String, List<String>>();

    public void intGraphData() {

        graph.put("1", Arrays.asList("2", "3"));
        graph.put("2", Arrays.asList("1", "4", "5"));
        graph.put("3", Arrays.asList("1", "6", "7"));
        graph.put("4", Arrays.asList("2", "8"));
        graph.put("5", Arrays.asList("2", "8"));
        graph.put("6", Arrays.asList("3", "9"));
        graph.put("7", Arrays.asList("3", "9"));
        graph.put("8", Arrays.asList("4", "5"));
        graph.put("9", Arrays.asList("6", "7"));
//        图结构如下
//          1
//        /   \
//       2     3
//      / \   / \
//     4  5  6  7
//      \ |  \ /
//        8    9

    }
    
    private Queue<String> queue = new LinkedList<String>();
    private Map<String, Boolean> status = new HashMap<String, Boolean>();

    public void BFS(String Point) {
        queue.add(Point);
        status.put(Point, false);
        bfsLoop();
    }

    private void bfsLoop() {
        String currentQueue = queue.poll();
        status.put(currentQueue, true);
        System.out.println(currentQueue);
        List<String> neighborPoints = graph.get(currentQueue);
        for (String poinit : neighborPoints)
        {
            if (!status.getOrDefault(poinit, false) )
            {
                if (queue.contains(poinit)) continue;
                queue.add(poinit);
                status.put(poinit, false);
            }
        }
        if (!queue.isEmpty() )
        {
            bfsLoop();
        }
    }

    private Stack<String> stack = new Stack<String>();
    public void DFS(String Point) {
        stack.push(Point);
        status.put(Point, true);
        dfsLoop();
    }

    private void dfsLoop() {
        if(stack.empty() )
        {
            return;
        }
        String stackPoint = stack.peek();
        List<String> neighbourPoints = graph.get(stackPoint);
        for (String point : neighbourPoints)
        {
            if (!status.getOrDefault(point, false) )
            {
                stack.push(point);
                status.put(point, true);
                dfsLoop();
            }
        }
        String popPoint =  stack.pop();
        System.out.println(popPoint);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请选择：深度遍历输入1，广度遍历输入0：");
        int choose = scan.nextInt();
        Looptest test = new Looptest();
        test.intGraphData();
        if(choose == 0)
        {
            System.out.println("广度优先遍历是：");
            test.BFS("1");}
        if(choose == 1)
        {
            System.out.println("深度优先遍历是： ");
            test.DFS("1");
        }

    }
}
